package com.j2boot.algorithm.string.sunday;

/**
 * sunday 字符串匹配算法
 *
 * @author yichengxian
 */
public class SundayStr {

    /**
     * @param master
     * @param slave
     * @return
     */
    public int sunday(char[] master, char[] slave) {
        //首先创建一个长度为123的数组 代表每个字符右移的距离
        int ascii_size = 123;
        //字符右移距离
        int[] move = new int[ascii_size];
        //主串长度
        int mSize = master.length;
        //子串长度
        int sSzie = slave.length;
        //同时对move数组做一个初始化,将其更新为子串长度+1
        for (int i = 0; i < ascii_size; i++) {
            move[i] = sSzie + 1;
        }
        //对于出现在子串中的每一个字符更新为其到末尾长度+1
        for (int i = 0; i < sSzie; i++) {
            move[slave[i]] = sSzie - i;
        }
        //同时初始化两个指针
        //开始匹配位置
        int start = 0;
        //已经匹配的长度
        int j;
        //当开始位置<子串的长度 遍可以结束循环
        while (start <= (mSize - sSzie)) {
            j = 0;
            //通过while循环逐位判断是否相等
            while (master[start + j] == slave[j]) {
                j++;
                if (j >= sSzie) {
                    return start;
                }
            }
            if ((start + sSzie) >= mSize) {
                return -1;
            }
            //当不匹配后,根据start+sSize得到最后一个下一个字符
            //最后一个字符的下一个字符
            char nextChar = master[start + sSzie];
            //查询该字符需要右移多少位并更新起始位置
            start += move[nextChar];
        }
        return -1;
    }

    public static void main(String[] args) {

        char[] master = "abcdefg".toCharArray();
        char[] slave = "cde".toCharArray();
        SundayStr sundayStr = new SundayStr();
        System.out.println(sundayStr.sunday(master, slave));
    }
}
